package cn.aylog.simpleTree;

/**
 * 数组模拟完全二叉树
 * 左节点 2*n+1
 * 右节点 2*n+2
 */
public class ArrayLikeBinaryTree {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree tree = new ArrayBinaryTree(arr);
        System.out.println("先序遍历");
        tree.preOrder(0); // 1 2 4 5 3 6 7
        System.out.println("中序遍历");
        tree.infixOrder(0); // 4 2 5 1 6 3 7
        System.out.println("后序遍历");
        tree.postOrder(0);// 4 5 2 6 7 3 1
    }
}

class ArrayBinaryTree {
    private int[] arr;

    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public int getLeftNodeIndex(int n) {
        int index = 2 * n + 1;
        if (index < arr.length) {
            return index;
        }
        return -1;
    }

    public int getRightNode(int n) {
        int index = 2 * n + 2;
        if (index < arr.length) {
            return index;
        }
        return -1;
    }

    /**
     * 先序遍历
     */
    public void preOrder(int n) {
        if(arr.length == 0) {
            System.out.println("数组为空");
            return;
        }
        if (n >= 0 && n <= arr.length) {
            System.out.println(arr[n]);
            int left = getLeftNodeIndex(n);
            if(left != -1) {
                preOrder(left);
            }
            int right = getRightNode(n);
            if(right != -1) {
                preOrder(right);
            }
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(int n) {
        if(arr.length == 0) {
            System.out.println("数组为空");
            return;
        }
        if (n >= 0 && n <= arr.length) {
            int left = getLeftNodeIndex(n);
            if(left != -1) {
                infixOrder(left);
            }
            System.out.println(arr[n]);
            int right = getRightNode(n);
            if(right != -1) {
                infixOrder(right);
            }
        }
    }

    /**
     * 先序遍历
     */
    public void postOrder(int n) {
        if(arr.length == 0) {
            System.out.println("数组为空");
            return;
        }
        if (n >= 0 && n <= arr.length) {
            int left = getLeftNodeIndex(n);
            if(left != -1) {
                postOrder(left);
            }
            int right = getRightNode(n);
            if(right != -1) {
                postOrder(right);
            }
            System.out.println(arr[n]);
        }
    }
}
